package leetcode.d23;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.ArrayList;
import java.util.List;

//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//[1,5,6,11,5,4]
public class Solution {

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int value = sum / 2;
        int[][] d = new int[nums.length][value + 1];
        //初始化
        for (int j = 1; j <= value; j++) {
            if (nums[0] <= j) {
                d[0][j] = nums[0];
            } else {
                d[0][j] = 0;
            }
            if (d[0][j] == value) {
                return true;
            }
        }

        for (int j = 1; j <= value; j++) {
            for (int i = 1; i < nums.length; i++) {
                if (j<nums[i]){
                    d[i][j] = d[i-1][j];
                }
                else{
                    d[i][j] = Integer.max(d[i - 1][j], d[i - 1][j - nums[i]] + nums[i]);
                }
                if (d[i][j] == value){
                    return true;
                }
            }
        }
        return false;

    }

    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int[] nums = {1, 5, 6, 11, 5, 4};
        boolean b = canPartition(nums);
        System.out.println(b);
    }
}
